Indexes are data structures used to process queries by providing relatively fast access to a set of data based on key values. Database systems historically have included one or two index types to enable database users to improve query processing performance. Each index type has its own advantages and disadvantages, and provides output in a particular format. The output format of each type of index largely dictates the type of operations for which the index type is best suited.
One type of index is a B-tree index. A B-tree index has branch nodes and leaf nodes. The branch nodes contain pointers to other nodes and data that indicates the range of values associated with the nodes to which they point. The leaf nodes store the index entries. Each index entry includes a [key, rowid] pair, where "key" is a particular key value and "rowid" is a row identifier that points to a particular row of a data table that contains that particular key value.
When a B-tree is used to process a query, the output of the B-tree index is a sequence of rowids. For example, use of a B-tree index built on a "first name" column to find records having a first name equal'to "Fred" would return the rowids from all of the index entries in the B-tree that contain the key value "Fred". Hence, if a data table had ten rows of data and rows 1, 2, 5, and 9 had "Fred" in the first name column, then the B-tree index would return the result "1, 2, 5, 9." The B-tree type index is particularly advantageous for data having uniqueness constraints.
Another type of index is a bitmap index. Bitmap indexes are similar to B-tree indexes except that each index entry in a bitmap index contains a [key, bitmap] pair, where "key" is a particular key value, "bitmap" is a series of bits, each bit in the bitmap corresponds to a row in the table associated with the bitmap index, and the value of each bit indicates whether the corresponding row contains the key value specified in the index entry. The bitmap index is particularly advantageous for data having a low cardinality. For example, a bitmap index would only have two index entries if built on a "gender" column of a table that can only contain two possible key values "M" and "F".
Using the above example where the first name "Fred" is found in rows 1, 2, 5, and 9, a bitmap index built on the same "first name" column would return the result "1100100010," to a search for the name "Fred". The first bit corresponds to the first row of data and the last bit corresponds to the tenth row of data. Since the bitmap returned by bitmap indexes is a Boolean value, bitmap indexes are particularly advantageous for processing queries that specify Boolean operations.
Conventional query processing techniques use only a single index type for a given query. For example, assume that a B-tree index is built on the "last name" column of a table, while a bitmap index is built on the "gender" column of the same table. Using conventional query processing, a query that specified values for both the last name and the gender (e.g. "last name=Johnson and gender=F") would either use the B-tree or the bitmap index, but not both.
Specifically, the B-tree index may be accessed to identify the rows that satisfy "last name=Johnson" criteria. These rows would be retrieved from the table and inspected to determine whether the value in the gender column satisfies the second criteria "gender=`F`". Alternatively, the bitmap index may be used to identify the rows that satisfy "gender=F". These rows would be retrieved from the table and inspected to determine whether the value in the "last name" column satisfies the criteria "last name=Johnson". In either case, only one type of index is used and, consequently, rows that do not satisfy the query have to be retrieved from the table and inspected.
Hence, there is a need for a mechanism that improves query processing by combining the use of different index types to minimize the rows of data that need to be retrieved from a table during query processing.